class Node:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right 
def traversal(root,lst):
    if not root: return 
    traversal(root.left,lst)
    lst.append(root)
    traversal(root.right,lst)
    
def solve(root):
    lst=[None]
    traversal(root,lst)
    lst.append(None)
    for i in range(1,len(lst)-1):
        print(lst[i].val,end=' ')
        lst[i].left=lst[i-1]
        lst[i].right=lst[i+1]
    return lst[1]

def build(lst):
    from collections import deque
    root=Node(lst[0])
    que=deque([root])
    i=1
    while len(que)>0 and i<len(lst):
        cur=que.popleft()
        if i<len(lst) and lst[i]:
            cur.left=Node(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right=Node(lst[i+1])
            que.append(cur.right)
        i+=2
    return root

def traversal_level(root):
    from collections import deque 
    que=deque([root])
    lst=[]
    while(len(que)>0):
        cur=que.popleft()
        if cur:
            lst.append(cur.val)
            que.append(cur.left)
            que.append(cur.right)
        else:
            lst.append(None)
    return lst

def output(root):
    print('***')
    cur=root
    nxt=cur.right
    while nxt:
        print(cur.val,end=' ')
        cur=nxt 
        nxt=nxt.right
    print(' ')
    while cur:
        print(cur.val,end=' ')
        cur=cur.left

root=build([10,6,14,4,8,12,16])
print(traversal_level(root))
root=solve(root)
output(root)

